package LeetCode;

import sun.nio.cs.ext.MacArabic;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName interview
 * @Description: TODO
 * @date ${DAT}22:33
 */
public class LeetCode111 {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    //没有简化前的
    // 自下而上的方法
    public int minDepth(TreeNode root) {
        if (root == null){
            return 0;
        }

        // 左孩子和右孩子都为空的情况，说明到达了叶子节点，直接返回1即可
        if (root.left ==null && root.right== null){
            return 1;
        }
        // 如果左孩子和右孩子其中一个为空，那么需要返回比较大的那个孩子的深度
        int m1 = minDepth(root.left);
        int m2 = minDepth(root.right);
        // 这里其中一个子节点为空，说明m1和m2有一个必然为0，所以可以返回m1 + m2 + 1(这个算式是，该节点的子节点的深度+自身的1)
        if (root.left == null || root.right == null){
            return m1 + m2 + 1;
        }

        // 最后一个情况，左右孩子都不为空，这个时候左右子树最小深度+1就行
        return Math.min(m1,m2) + 1;
    }

    public int minDepth2(TreeNode root){
        if (root == null){
            return 0;
        }

        // 左孩子和右孩子都为0的情况，说明到达叶子节点，直接返回1
        if (root.left == null && root.right == null){
            return 1;
        }

        // 继续递归算左孩子、右孩子的值
        int left = minDepth2(root.left);
        int right = minDepth2(root.right);

        if (root.left == null || root.right == null){
            return left + right + 1;
        }

        // 最后的情况，左右孩子都不为空
        return Math.min(left,right) + 1;
    }
}

